﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// 최대흐름 알고리즘
    /// O(F * E)
    /// </summary>
    class FordFulkerson
    {
        private List<Edge>[] G;
        bool[] used;
        int maxSize;
        public FordFulkerson(int maxSize)
        {
            this.maxSize = maxSize;
            G = new List<Edge>[maxSize];
            for (int i = 0; i < G.Length; i++)
            {
                G[i] = new List<Edge>();
            }
            
        }
        /// <summary>
        /// from에서 to로 용량 cap의 변을 추가
        /// </summary>
        public void AddEdge(int from, int to, int cap)
        {
            G[from].Add(new Edge(0, to, 0, cap, G[to].Count));
            G[to].Add(new Edge(0, from, 0, 0, G[from].Count - 1));
        }

        public int MaxFlow(int s, int t)
        {
            int flow = 0;
            for (; ; )
            {
                used = new bool[maxSize];
                int f = Dfs(s, t, int.MaxValue);
                if(f == 0) return flow;
                flow += f;
            }
        }

        private int Dfs(int v, int t, int f)
        {
            if (v == t) return f;
            used[v] = true;
            for (int i = 0; i < G[v].Count; i++)
            {
                Edge e = G[v][i];
                if (!used[e.To] && e.Cap > 0)
                {
                    int d = Dfs(e.To, t, Math.Min(f, e.Cap));
                    if (d > 0)
                    {
                        e.Cap -= d; //flow를 흐르는 만큼 cap를 줄여줌
                        Edge g = G[e.To][e.Rev]; //역변
                        g.Cap += d;
                        return d;
                    }
                }
            }
            return 0;
        }
    }
}
